a. Field of the Invention
The present invention concerns matching entities based on attributes of the entities and predicting an attribute of an entity based on attributes of the entity and other entities. More specifically, the present invention concerns xe2x80x9ccollaborative filteringxe2x80x9d which may be used, for example, to suggest content of interest to a client entity on a network (e.g., the Internet).
b. Related Art
In the past five to ten years, computers have become interconnected by networks to an ever increasing extent via the Internet. The proliferation of networks, in conjunction with the increased availability of inexpensive data storage means, has afforded computer users unprecedented access to a wealth of data. Unfortunately, however, the very vastness of available data can overwhelm a user. Desired data can become difficult to find and search heuristics employed to locate desired data often return unwanted data.
Various concepts have been employed to help users locate desired data. In the context of the Internet for example, some services have organized content based on a hierarchy of categories. A user may then navigate through a series of hierarchical menus to find content that may be of interest to them. An example of such a service is the YAHOO(trademark) World Wide Web site on the Internet. Unfortunately, content, in the form of Internet xe2x80x9cweb sitesxe2x80x9d for example, must be organized by the service and users must navigate through menus. If a user mistakenly believes that a category will be of interest or include what they were looking for, but the category turns out to be irrelevant, the user must backtrack through one or more hierarchical levels of categories. Moreover, such services which provide hierarchical menus of categories are passive. That is, a user must actively navigate through the hierarchical menus of categories.
Again in the context of the Internet for example, some services provide xe2x80x9csearch enginesxe2x80x9d which search database content or xe2x80x9cweb sitesxe2x80x9d pursuant to a user query. In response to a user""s query, a rank ordered list, which includes brief descriptions of the uncovered content, as well as hypertext links (text, having associated Internet address information, which, when activated, commands a computer to retrieve content from the associated Internet address) to the uncovered content is returned. The rank ordering of the list is typically based on a match between words appearing in the query and words appearing in the content. Unfortunately, however, present limitations of search heuristics often cause irrelevant content to be returned in response to a query. Again, unfortunately, the very wealth of available content impairs the efficacy of these search engines since it is difficult to separate irrelevant content from relevant content. Moreover, as was the case with services which provide hierarchical menus of categories, search engines are passive. That is, a user must actively submit a query.
The two above-mentioned content search concepts are categorized as xe2x80x9cpullxe2x80x9d processes because the user must explicitly direct these processes to find the content and pull it to them (i.e., to their computer).
In view of the drawbacks of the above discussed data location concepts, xe2x80x9ccollaborative filteringxe2x80x9d systems have been developed. Collaborative filtering systems predict the preferences of a user based on known attributes of the user, as well as known attributes of other users. Some collaborative filtering systems require that a user fill out a survey of his(her) interests and use the submitted survey as a query. Hence, such collaborative filtering systems may be classified as xe2x80x9cpullxe2x80x9d processes. Other collaborative filtering systems are categorized as xe2x80x9cpushxe2x80x9d processes because they use content previously xe2x80x9cconsumedxe2x80x9d (e.g., requested, downloaded, rendered, etc.) by a user to proactively predict content which may appeal to that user. Such collaborative filtering systems then present (or xe2x80x9cpushxe2x80x9d) the content, or information identifying the content, to the user.
Basically, collaborative filtering uses known attributes (e.g., explicitly entered votes) of a new user (referred to as xe2x80x9cthe active casexe2x80x9d) and known attributes of other users to predict values of unknown attributes of the new user (e.g., attributes not yet entered by the new user). The mean vote ({overscore (vi)}) for an entity may be defined as:                                           v            i                    _                =                              1                          m              i                                ⁢                                    ∑                              j                ∈                                  I                  i                                                      ⁢                          v                              i                ,                j                                                                        (        1        )            
where
Vi,jxe2x89xa1A value of attribute j of entity i. Typically, an integer value.
mxe2x89xa1The number of attributes (e.g., in a database).
Iixe2x89xa1A set of attribute indexes for which entity i has known values (e.g., based on an explicitly entered vote). For example, I2={3,4} means that entity 2 has values (e.g., has voted) for attributes 3 and 4.
Mixe2x89xa1The number of attributes for which entity i has known valuesxe2x80x94the number of elements in Ii.
Denoting parameters for the active case (i.e., new entity) with subscript a, a prediction pa,j of active case attribute values (e.g., votes) for attributes without known values (i.e., attributes not in Ia) can be defined as:                               p                      a            ,            j                          =                                            v              _                        a                    +                                    ∑                                                i                  =                  1                                ,                n                                      ⁢                                          (                                                      v                                          i                      ,                      j                                                        -                                                            v                      i                                        _                                                  )                            ⁢                              w                                  a                  ,                  i                                                                                        (        2        )            
nxe2x89xa1The number of entities (e.g., in a database).
Wa,ixe2x89xa1The estimated weight (or alternatively match) between entity i and entity a.
pi,jxe2x89xa1The predicted value of attribute j of entity i.
Hence, a predicted attribute value (e.g., vote) is calculated from a weighted sum of the attribute values (e.g., votes) of each other user. The appearance of mean values in the formula merely serves to express values in terms of deviation from the mean value (i.e., defines a reference) and has no other significant impact.
An example of a proposed collaborative filtering system is discussed in the article, Resnick et al., xe2x80x9cGroupLens: An Open Architecture for Collaborative Filtering of Netnews,xe2x80x9d Proceedings of the Association for Computer Machinery 1994 Conference on Computer Supported Cooperative Work, Chapel Hill, N.C., pp. 175-186 (1994) (hereafter referred to as xe2x80x9cthe Resnick articlexe2x80x9d). In the system discussed in the Resnick article (hereafter referred to as xe2x80x9cthe Grouplens systemxe2x80x9d), users rate articles which they have read. Rating servers, called Better Bit Bureaus, gather and disseminate the ratings. More specifically, the Better Bit Bureaus package one or more ratings into a news article. The rating servers predict scores based on a heuristic that people who agreed in the past will probably agree again. More specifically, the GroupLens system first correlates ratings to determine the similarity of a user""s ratings with the ratings of other users. Correlation coefficients or weights between xe2x88x921 and 1 are computed and indicate how much a particular user tended to agree with other users. The GroupLens system then predicts how much the user will like a new article based on ratings from similar users. More specifically, the ratings of the other users are weighted based on the correlation coefficients determined above and the weighted ratings are combined to form a prediction.
Unfortunately, the GroupLens system has a number of problems. First, users must explicitly enter ratings. Some users find it difficult to judge articles or other content. In this regard, it is expected that predictions made by the GroupLens system will improve as correlation or weight determinations improve. It is further expected that the correlation and weight determinations made by the GroupLens system will improve as more ratings are entered. Unfortunately, many users may become frustrated by poor predictions and/or with entering ratings before enough ratings are gathered to make the correlation and weight determinations made by the GroupLens system good. Thus, the GroupLens system has a bootstrapping problem. Many users will become frustrated with the predictions made by the GroupLens system, due, in part, to an initial scarcity of ratings. As a result of user frustration with initially poor predictions, such users may stop entering ratings. If this occurs, the predictions made by the GroupLens system will probably not improve because users will not provide it with enough ratings information.
Moreover, the correlation strategy used in the GroupLens system apparently does not consider the distinctness of the ratings. For example, the fact that two users might like a popular article is apparently not weighted less than the fact that two users might like an very unpopular article. Furthermore, the GroupLens system apparently does not consider non-data, or the absence of ratings by users.
Thus, improved content location methods and apparatus are needed. Since burdens formerly placed on the entity (e.g., a computer user) should be eliminated to the extent possible, such methods and apparatus (i) should be useable in content push systems, such as collaborative filtering systems for example, and (ii) should use entity attributes which may be explicitly and/or implicitly determined. Since the content should be only the most relevant or most likely to be of interest to the entity, such methods and apparatus should accurately match entities based on attributes of the entities and should accurately predict attributes of (e.g., content of interest to) an entity based on attributes of the entity and other entities. Finally, the methods and apparatus should be able to operate on a distributed environment, such as a networked environment including clients and servers.
The present invention provides various ways to enhance collaborative filtering processes, for example, by enhancing processes for matching entities. More specifically, a first way of enhancing a process for matching entities in accordance with the present invention is to adjust the value (Vi,j) of an attribute of an entity based on the number of entities that have a value for (e.g., have voted on) that particular attribute. In general, the value (Vi,j) of the attribute of an entity will be decreased as the number of entities that have a value of the attribute increases. Referred to as xe2x80x9cinverse attribute frequencyxe2x80x9d, this aspect of the present invention lowers the effect of more common attributes in generating recommendations. The present invention can operate with many types of entities (e.g., a computer, a local area network, a business, etc.) and many different attributes (e.g., age, sex, weight, favorite food, television shows viewed, money spent on movie rentals, etc.).
In a second way of enhancing a process for matching entities in accordance with the present invention, a match of entities is based on a union of all attributes for which either entity has a value, rather than only attributes for which both entities have values. This aspect of the present invention is referred to below as xe2x80x9cattribute set harmonizationxe2x80x9d. Default values may be provided to attributes without values. Such values may be referred to as xe2x80x9cdefaultxe2x80x9d or xe2x80x9cimplicitxe2x80x9d values.
In a similar concept, still another aspect of the present invention improves a process for matching entities by determining a match of entities based on attributes for which neither entity has values. Referred to as xe2x80x9cattribute expansionxe2x80x9d, this aspect of the present invention is useful when most attributes can be assumed to have little relevance to most entities. As with xe2x80x9cattribute set harmonizationxe2x80x9d, default values may be provided to attributes without values.
In a way of enhancing a process for collaborative filtering in accordance with yet another aspect of the present invention, the weights used for collaborative filtering prediction (e.g., the basic collaborative filtering prediction formula discussed above) are tuned to emphasize relatively high weights and to suppress relatively low weights. This aspect of the present invention is referred to below as xe2x80x9ctuningxe2x80x9d or xe2x80x9camplificationxe2x80x9d.
A tuned weight Wxe2x80x2 may be defined as:
wxe2x80x2=wp if wxe2x89xa70
wxe2x80x2=xe2x88x92(xe2x88x92wp) if w less than 0
where p1xe2x89xa1A tunable parameter, typically greater than 1.
The aspects of the present invention may be used in content push systems, such as certain collaborative filter systems for example, so that burdens on a user are minimized. Also, the aspects of the present invention may operate on a distributed environment, such as a networked environment including clients and servers. More specifically, in the context of the Internet, the present invention may be employed to predict Internet locations or content that may be of interest to an end user. The present invention may operate (a) locally, at a client, (b) remotely, at a server, or (c) at a location remote from the client and the server (e.g., a separate server). Finally, particular functions of the present invention may be distributed at one or more of the above devices (or locations).